package first.forHuaWei.codeTop;

import java.util.Arrays;

public class LC1552 {
    // 两球之间的磁力
    public static void main(String[] args) {

    }

    // 二分法开始搜索
    public int maxDistance(int[] position, int m) {
        // 先对数组排序
        Arrays.sort(position);
        int i = 1;
        int j = position[position.length-1]-position[0];
        int result = -1;
        while (i <= j) {
            int x = (i+j) / 2;
            if (check(x, position, m)) {
                result = x;
                i = x + 1;
            } else {
                j = x - 1;
            }
        }
        return result;
    }

    // 检查当前这种放置方法是否合法,间隔是x,将这m个球放到数组的杯子中
    public static boolean check(int x, int[] position, int m) {
        int count = 1;
        int pre = position[0];
        for (int i=1; i<position.length; i++) {
            if (position[i] - pre >= x) {
                pre = position[i];
                count++;
            }
        }
        return count >= m;
    }
}
